package com.github.hgkmail.hello.leetcode101.binarysearch;

public class LC540SingleElementInASortedArray {
    //检查值是否相同，考虑越界
    public boolean isSame(int[] nums, int i, int j) {
        if (i>=0 && i<nums.length && j>=0 && j<nums.length && nums[i]==nums[j]) {
            return true;
        }
        return false;
    }

    //检查是否奇数 odd
    public boolean isOdd(int x) {
        return x%2==1;
    }

    public int singleNonDuplicate(int[] nums) {
        //base case
        if (nums.length==1) {
            return nums[0];
        }
        //查找一个数，使用左闭右闭
        int l=0;
        int r=nums.length-1;
        int mid;
        while (l<=r) {
            mid=l+(r-l)/2;
            if (!isSame(nums, mid, mid-1) && !isSame(nums, mid, mid+1)) { //与两边的数不同，是独立数
                return nums[mid];
            }
            //独立数还未出现：奇数位与前一位相同，偶数位与后一位相同
            if ((isOdd(mid) && isSame(nums, mid, mid-1)) || (!isOdd(mid) && isSame(nums, mid, mid+1))) {
                l=mid+1;
            } else { //独立数已经出现：奇数位与后一位相同，偶数位与前一位相同
                r=mid-1;
            }
        }

        return 0;
    }
    public static void main(String[] args) {
        System.out.println(new LC540SingleElementInASortedArray().singleNonDuplicate(new int[]{1,1,2}));
    }
}
